//704.二分查找
var search=function(nums,target){
    var left=0;
    var right=nums.length;   
    while(left<=right){
        var middle=left+Math.floor((right-left)/2);
        if(nums[middle]>target){
            right=middle-1;
        }else if(nums[middle]<target){
            left=middle+1;
        }else{
            return middle;
        }
    }
    return -1;
}

//35.搜索插入位置
var searchInsert=function(nums,target){
    var left=0;
    var right=nums.length-1;
    var ans=nums.length
    while(left<=right){
        var middle=left+Math.floor((right-left)/2);
        if(nums[middle]>target){
            right=middle-1;
        }else{
            ans=nums[middle];
            left=middle+1;
        }
    }
    return ans;
}

//34.在排序数组中查找元素的第一个和最后一个位置
//寻找的是第一个等于的target(left) 和 第一个大于target的值减一(right) 所以后面right要减一 
// 为了代码的复用用 lower来判断是左边还是右边 
// 左边为true 查找第一个等于的值 右边为false 查找第一个大于的值
// 最后判断是否符合条件 符合就返回，否则返回[-1,-1]

const Search=(nums,target,lower)=>{
    var left=0;
    var right=nums.length-1;
    var ans=nums.length;
    while(left<=right){
        var middle=left+Math.floor((right-left)/2);
        if(nums[middle]>target||(lower && nums[middle]>=target)){
            right=middle-1;
            ans=middle;
        }else{
            left=middle+1;
        }
    }
    return ans;
} 
var searchRange = function(nums, target) {

let ans=[-1,-1];
var leftsearch=Search(nums,target,true);
var rightsearch=Search(nums,target,false)-1;
if(leftsearch<=rightsearch&&rightsearch<nums.length&&nums[leftsearch]==target&&nums[rightsearch]==target){
    ans=[leftsearch,rightsearch];
    
}
return ans;

};



// 69.x的平方根 
// 简单方法：使用sqrt
// 使用二分法 返回right
var mySqrt = function(x) {
    var left=0;
    var right=x;
    while(left<=right){
        var middle=left+((right-left)>>1);
        if(middle*middle>x){
            right=middle-1;
        }else{
            left=middle+1;
        }
    }
    return right;
};


// 367. 有效的完全平方数
/**
 * @param {number} num
 * @return {boolean}
 */
 var isPerfectSquare = function(num) {
    var left=0;
    var right=num;
    while(left<=right){
        var mid=left+((right-left)>>1);
        if(mid*mid>num){
            right=mid-1;

        }else{
            left=mid+1;
        }
    }
    if(right*right==num){
        return true;
    }else{
        return false;
    }
    
};